package 力扣题库;

public class p236二叉树的最近公共祖先 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //LCA 最近公共祖先
        if (root==null) return null;

        if (root==p || root==q) {
            //递归出口
            return root;
        }

        TreeNode left=lowestCommonAncestor(root.left,p,q);//去左子树找 p/q
        TreeNode right=lowestCommonAncestor(root.right,p,q);////去右子树找 p/q

        //当去左右子树寻找 p/q，返回值均不为空，则p/q的最近公共祖先为 root
        if (left !=null && right!=null) {
            return root;
        }

        //当只有左子树返回值不为空，则最近公共祖先则为left
        if (left!=null) {
            return left;
        }
        //当只有右子树返回值不为空，则最近公共祖先则为right
        if (right!=null) {
            return right;
        }

        //左右子树返回值均为空，则没有找到 p/q
        return null;
    }
}
